import java.util.ArrayList;
import java.util.List;

public class 最后一块石头的重量II {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        // 算出 sum
        for(int stone : stones) {
            sum += stone;
        }
        // 直接进行空间压缩的背包
        int m = sum / 2;
        boolean[] dp = new boolean[m + 1];
        // 0 个石头可以满足大小为 0, 初始化成 true
        dp[0] = true;
        // 正常 01 背包直接套模板了
        for(int stone : stones) {
            for(int j = m;j >= stone;j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }
        // 遍历一下最大值是多少, 找到了直接 sum - j 是其中一堆的最大值, 减去另一堆
        for(int j = m;j >= 0;j--) {
            if(dp[j]) {
                return sum - j - j;
            }
        }
        return -1;
    }
}
